package utils {
	
	public class FactoradicNumber {
		protected var _length:int;
		protected var _number:Number;
		public var fitness:int;
		
		function FactoradicNumber(length:int, n:Number = 0) {
			if(length <= 0) throw new Error('length has to be positive');
			_length = length;
			_number = n;
			if(_number < 0) {
				setRandom();
			}
		}
		
		public function get number():Number { return _number; }
		public function set number(n:Number):void { _number = n; }
		
		public function get length():int { return _length; }
		
		public function get maximum():Number { return factorial(_length); }
		
		public function setNumberFromPermutation(perm:Array):FactoradicNumber {
			if(perm.length != _length) throw new Error('Invalid array length');
			this.setNumberFromLehmer(permutationToLehmer(perm));
			return this;
		}
		
		public static function makeNumberFromPermutation(perm:Array):FactoradicNumber {
			var newNumber:FactoradicNumber = new FactoradicNumber(perm.length, 0);
			newNumber.setNumberFromLehmer(permutationToLehmer(perm));
			return newNumber;
		}
		
		public function setRandom():void {
			_number = Math.floor(Math.random() * factorial(_length));
		}
		
		public function getLehmer():Array {
			var n:Number = _number;
			var factoradic:Array = [0];
			var j:Number = 2;
			while(j <= _length) {
				var rem:int = n % j;
				factoradic.unshift(rem);
				n = (n - rem) / j;
				j++;
			}
			return factoradic;
		}
		
		public function setNumberFromLehmer(lehmer:Array):FactoradicNumber {
			if(lehmer.length != _length) throw new Error('Invalid Lehmer length');
			_number = 0;
			var dFac:Number = 1; 
			for(var d:int = lehmer.length-1; 0<=d; d--) {
				_number += lehmer[d]*dFac;
				dFac *= (lehmer.length-d);
			}
			return this;
		}
		
		public function permutation():Array {
			var k:Number = _number;
			var r:Array = [];
			var j:int = 1;
			var i:int;
			var p:int;
			r[_length-j] = 0;
			while(j++ < _length){
				p = i = _length-j;
				r[p] = Math.floor((k/=(j-1))%j);
				while(i++ < _length) {
					if(r[i] >= r[p]) ++r[i];
				}
			}
			return r;
		}
		
		public function permutateArray(n:Array):Array {
			if(n.length != _length) throw new Error('Invalid array length');
			var r:Array = permutation();
			for(var i:int = 0; i < _length; i++)
				r[i] = n[r[i]];
			return r;
		}
		
		public static function factorial(n:Number):Number {
			if(n>1) return n*factorial(n-1);
			return 1;
		}
		
		public static function permutationToLehmer(perm:Array):Array {
			var lehmer:Array = new Array();
			for(var i:int = 0; i < perm.length; i++) {
				var li:int = 0;
				for(var j:int = i+1; j < perm.length; j++) {
					if(perm[j] < perm[i]) li++;
				}
				lehmer[i] = li; // = |{j > i : perm[j] < perm[i]}|
			}
			return lehmer;
		}
		
		// Genetic algorithm stuff
		public function localSwapMutateOnce():void {
			if(_length <= 1) return;
			var perm:Array = permutation();
			var spot:int = Math.floor(Math.random() * (_length - 1));
			// swap spot and spot+1
			var temp:int = perm[spot];
			perm[spot] = perm[spot+1];
			perm[spot+1] = temp;
			this.setNumberFromPermutation(perm);
		}
		
		public function swapMutateOnce():void {
			if(_length <= 1) return;
			var perm:Array = permutation();
			var spotA:int = Math.floor(Math.random() * _length);
			var spotB:int = Math.floor(Math.random() * _length);
			// swap spotA and spotB
			var temp:int = perm[spotA];
			perm[spotA] = perm[spotB];
			perm[spotB] = temp;
			this.setNumberFromPermutation(perm);
		}
		
		public function shiftMutateOnce():void {
			if(_length <= 1) return;
			var perm:Array = permutation();
			var spotA:int = Math.floor(Math.random() * _length);
			var spotB:int = Math.floor(Math.random() * _length);
			var spotMin:int = Math.min(spotA, spotB);
			var spotMax:int = Math.max(spotA, spotB);
			// swap spotA and spotB
			var temp:int, i:int
			if(Math.random() < 0.5) {
				temp = perm[spotMin];
				for(i = spotMin; i < spotMax; i++) perm[i] = perm[i+1];
				perm[spotMax] = temp;
			} else {
				temp = perm[spotMax];
				for(i = spotMax; spotMin < i; i--) perm[i] = perm[i-1];
				perm[spotMin] = temp;
			}
			this.setNumberFromPermutation(perm);
		}
		
		public function clone():FactoradicNumber {
			return new FactoradicNumber(_length, _number);
		}
		
		public static function cross(a:FactoradicNumber, b:FactoradicNumber):FactoradicNumber {
			if(a.length != b.length) throw new Error('Can not cross two different numbers');
			var aLehmer:Array = a.getLehmer();
			var bLehmer:Array = b.getLehmer();
			var newLehmer:Array = new Array();
			for(var i:int = 0; i < a.length; i++) {
				newLehmer.push((Math.random() < 0.5)?aLehmer[i]:bLehmer[i]);
			}
			return (new FactoradicNumber(a.length, 0)).setNumberFromLehmer(newLehmer);
		}
	}
}